package LRU

/*
绿色的是字典(map)，存储键和值的映射关系。这样根据某个键(key)查找对应的值(value)的复杂是O(1)，
在字典中插入一条记录的复杂度也是O(1)。
红色的是双向链表(double linked list)实现的队列。将所有的值放到双向链表中，这样，当访问到某个值时
将其移动到队尾的复杂度是O(1)，在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。
*/

import (
	"container/list"
)

type Cache struct {
	maxBytes  int64                         //允许使用的最大内存
	nbytes    int64                         //当前已使用的内存
	ll        *list.List                    //双向链表
	cache     map[string]*list.Element      //哈希map
	OnEvicted func(key string, value Value) //是某条记录被移除时的回调函数 可以为nil
}

func NewCache(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes:  maxBytes,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}

//entry 是双向链表节点的数据类型，在链表中仍保存每个值对应的 key 的好处在于，
//淘汰队首节点时，需要用 key 从字典中删除对应的映射。
type entry struct {
	key   string
	value Value
}

//Value 许值是实现了 Value 接口的任意类型，该接口只包含了一个方法 Len() int，
//用于返回值所占用的内存大小。
type Value interface {
	Len() int
}

//Len 缓存条目的数量
func (c *Cache) Len() int {
	return c.ll.Len()
}

func (c *Cache) Get(key string) (value Value, ok bool) {
	//从字典中找到对应的双向链表
	//将该节点移动到队尾
	if ele, ok := c.cache[key]; ok { //如果对应的链表节点存在 将其移动到队尾并返回查找的值
		c.ll.MoveToFront(ele) //将链表结点ele移动到队尾（双向链表队首队尾是相对的）
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

func (c *Cache) RemoveOld() {
	ele := c.ll.Back() //取首节点
	if ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)
		c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

//Add 新增缓存
func (c *Cache) Add(key string, value Value) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		c.nbytes += int64(value.Len()) - int64(kv.value.Len())
		kv.value = value
	} else {
		ele1 := c.ll.PushFront(&entry{key, value})
		c.cache[key] = ele1
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOld()
	}
}
